#include <iostream>
#include <time.h>
#include <fstream>

using std::endl;
using std::cout;
using std::ofstream;

void swap (int &a, int &b)
{
	int t = a;
	a = b;
	b = t;
}

void QuickSort(int* arr, int first, int last, int &compareCount, int &swapCount)
{
	int i = first, j = last, x = arr[(first + last) / 2];

	do {
		while (arr[i] < x) i++;
		while (arr[j] > x) j--;

		if(i <= j) {
			compareCount++;
			if (i < j) 
			{
				swapCount++;
				swap(arr[i], arr[j]);
			}
			i++;
			j--;
		} 
else compareCount++;
	} while (i <= j);

	if (i < last)
		QuickSort(arr, i, last,compareCount,swapCount);
	if (first < j)
		QuickSort(arr, first,j, compareCount,swapCount);
}

int main()
{
	const int n =  11;
	int **arr;
	int *compareCount; 
	int *swapCount;
	ofstream out("output.csv");
	if(!out)
	{
		cout<<"NO FILE => NO SORTING";
		return 1;
	}
	arr = new int*[n];
	compareCount = new int[n];
	swapCount = new int[n];
	srand (time(NULL));

	for(int i = 1, j = 0 ; j < n ; i<<=1, ++j)
	{
		compareCount[j] = 0;
		swapCount[j] = 0;
		arr[j] = new int[i];		
	}

	for(int t = 0; t < 100; ++t)
	{
		for(int i = 1, j = 0; j < n; i<<=1, ++j)
		{
			for(int k = 0; k < i; ++k)
			{
				arr[j][k] = rand() % 1000;
			}
			QuickSort(arr[j],0, i-1,compareCount[j],swapCount[j]);
		}
	}
	for(int i = 1, j = 0 ; j < n ; i<<=1, ++j)
	{
		cout<<"Average compare count on size "<<i<<" = "<<compareCount[j]/100<<endl;
		out<<i<<";"<<compareCount[j]/100.0<<";";
		cout<<"Average swap count on size "<<i<<" = "<<swapCount[j]/100<<endl<<endl;
		out<<swapCount[j]/100.0<<endl;
	}

	for(int i = 0; i < n; ++i)
	{
		delete [] arr[i];
	}
	delete [] arr;
	out.close();

	return 0;
}